package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         328,
		Discription: "奇节点相连，偶节点相连，奇链表的最后一个节点连偶链表的第一个节点",
		Level:       2,
		Labels: map[string]int{
			"链表":    1,
			"双指针滑动": 1,
		},
	})
}

func OddEvenList(head *ds.ListNode) *ds.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	//维护一个奇链表的当前节点、偶链表的当前节点和偶链表的第一个节点（head.Next）
	oddCur := head
	evenHead := head.Next
	evenCur := head.Next
	cur := evenCur.Next
	isOdd := true
	for cur != nil {
		if isOdd {
			oddCur.Next = cur
			oddCur = cur
		} else {
			evenCur.Next = cur
			evenCur = cur
		}
		cur = cur.Next
		isOdd = !isOdd
	}

	oddCur.Next = evenHead
	evenCur.Next = nil
	return head
}
